home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 001-025 / disk_006 / sort / qksort.c next >
C/C++ Source or Header  |  1992-05-06  |  12KB  |  394 lines
  1. /*--- EDIT # 0128    13 Apr 1982    9:14:42    DB1:[21,6]QKSORT.C;237  */
  2. /*--- PREVIOUS EDIT    12 Apr 1982   15:17:02    DB1:[21,6]QKSORT.C;235  */
  3.  
  4. /*
  5.     .title    qksort
  6. ;+
  7. ; index sort an array
  8. ; index quicksort
  9. ;
  10. ; usage
  11. ;    qksort(array, num_elements, elt_size, qkcmp);
  12. ;    ??? array[];        The array to sort.
  13. ;    unsigned int num_elements;    The number of elements in
  14. ;                    the array.
  15. ;    int elt_size;        sizeof an array element.
  16. ;    int (*qkcmp)();        user-supplied routine which
  17. ;                compares two array elements.
  18. ;
  19. ; description
  20. ;    Sort the array. The user must supply the routine which qksort
  21. ;    calls to compare two array elements. The routine is called as:
  22. ;    "qkcmp(a, b)  BYTE *a, *b;", and must return
  23. ;    a value just like strcmp does:
  24. ;        a < b  returns -1
  25. ;        a == b returns 0
  26. ;        a > b  returns +1
  27. ;
  28. ;    For example:
  29. ;     int int_array[10];    integer array
  30. ;     char *str_array[10];    array of pointers to strings
  31. ;     qksort(int_array, 10, sizeof(int), &int_cmp);
  32. ;     qksort(str_array, 10, sizeof(char *), &str_cmp);
  33. ;     *********************
  34. ;     int_cmp(a, b)
  35. ;     int *a, *b;
  36. ;     {
  37. ;     return (*a - *b);
  38. ;     }
  39. ;
  40. ;     **********************
  41. ;     str_cmp(a, b)
  42. ;     char *a[], *b[];
  43. ;     {
  44. ;     return (strcmp(*a, *b));
  45. ;     }
  46. ;
  47. ; bugs
  48. ;    The performance is best if array elements are aligned on
  49. ;    word boundaries. This will be the case if the array is of
  50. ;    int's, etc, or pointers to strings. The obvious choice for
  51. ;    strings is for it to be an array of pointers to
  52. ;    strings, anyway.
  53. ;
  54. ;    This routine is NOT recursive, requires minimal stack space,
  55. ;    and is efficient for any existing order in the original array,
  56. ;    even if it is already sorted, in reverse order, or
  57. ;    has all equal elements.
  58. ;
  59. ;    This is the slickest quicksort I have ever come across, and I
  60. ;    have been collecting them for several years.
  61. ;
  62. ; Author:
  63. ;     Ray Van Tassle
  64. ;     13 Apr 1982
  65. ;-
  66. */
  67. /*
  68.  * Super quickersort.
  69.  * This one is non-recursive.
  70.  *
  71.  * by Ray Van Tassle    Feb, 1982
  72.  *
  73.  * This is essentially 'program 2' from R. Sedgewick,
  74.  * "Implementing Quicksort Programs", Comm ACM, Oct 1978 p 847-856.
  75.  * I tried several other variants of quicksort (I have amassed a
  76.  * very large collection of books and articles on quicksort over
  77.  * the years), and most of them turn out to not be improvements at
  78.  * all. It is really surprising to find that an "obvious
  79.  * improvement" degrades the performance substantially!
  80.  * I found that the only way to check out variations was to code it up
  81.  * and run it with a driver program. The one I used generates 500, 5000,
  82.  * or 20000 random numbers and calls qksort 5 times each with these
  83.  * differences: 1) from the random number generator, 2) the same, but
  84.  * modulo 50, to give lots of equal keys, and 3)with the array already sorted.
  85.  * I must report that this version is very slightly worse than the one
  86.  * on the Structured Language tape spring 81 for case #1, very slightly
  87.  * better for case #2, and a lot better for case #3 (the old one could
  88.  * not handle a sorted array, and would blow sky high).
  89.  *
  90.  * The quicksort by Bob Denny and Tim Coad on the RSX Fall81 tape is
  91.  * two times longer than the old Decus one for case #1 &2, but
  92.  * will handle sorted arrays.
  93.  * This version is twice as fast as the Denny/Coad version for case 1 & 2,
  94.  * and slightly faster for case #3.
  95.  *
  96.  * So.......a word to would be improvers:
  97.  *    Before inserting your favorite improvement to this quicksort,
  98.  *    put it to a good test, ad make sure that you are not
  99.  *    actually fouling it up.
  100.  * I spent literally dozens and dozens of hours of CPU time running
  101.  * tests.
  102.  *
  103.  *
  104.  *   Test run times for 5 runs, in seconds "lowest" - highest".
  105.  *   times for 5000 elements (int). On an 11/70 with cache and
  106.  *    nothing else running. (The tests are compute bound).
  107.  *    Old decus    Denny/Coad    RVT
  108.  * #1    4.2 - 4.5    6.5 - 7.1    3.4 - 3.6
  109.  * #2    4.5 - 4.7    5.0 - 5.4    2.8 - 2.8
  110.  * #3    !bombs!        2.6 - 2.8    2.0 - 2.1
  111.  *
  112.  * These times are using "copy" to swap array members, which
  113.  * means that the qksort can handle elements of any arbitrary size. The
  114.  * actual decus & Denny/Coad code on the tapes do the swap by
  115.  * just moving the 'int'. This version of the old decus one takes
  116.  * about a second longer (the times shown above) than the one on the
  117.  * tapes, which move int's. So in reality, when you compare like to like,
  118.  * my version (this one) is actually faster than the old decus one.
  119.  *
  120.  *
  121.  * We select the pivot element to be the median element of the 1st, last,
  122.  * and middle elements of the segment.
  123.  * 
  124.  * Partitioning is not really that great for small segments (too much
  125.  * overhead), so these
  126.  * are done by an insertion sort, which is known to be quite
  127.  * efficient for small segments. It is claimed that the best way to
  128.  * do it is to ignore these small segments during the partitioning,
  129.  * then run the entire array thru the insertionsort. This takes only
  130.  * slightly longer than doing the individual segments, but the
  131.  * set-up overhead price is paid only once.
  132.  * The partitioning leaves these small segments
  133.  * in the right spot, just out of sort within themselves, so we
  134.  * never have to move more elements than those within each segment.
  135. */
  136. #define TRYMAIN        /* Make a main testing program */
  137. #undef TRYMAIN
  138.  
  139. #define LOW_BOUND 13    /* Smaller segments will be done differently */
  140. #define BYTE char
  141. /* Treat the array as bytes, as we really want
  142.              * to use 'elt_size', but C doesn't allow this,
  143.              * so we do it ourselves. */
  144.  
  145. #define INT_MSK 1   /* to mask the addr to see if it is on an int boundary */
  146.  
  147. #define LOC_SIZ 10    /* size of a local pivot area */
  148.  
  149. static int typ_swap = 0;    /* TRUE if we can swap by moving int's
  150.                  * else we have to move bytes */
  151. static int move_size = 0;    /* number of byte/int's to move (elt_size)*/
  152.  
  153. #ifdef AMIGA || unix
  154. char *alloc (size)
  155. int size;
  156. {
  157.     return (calloc (size, sizeof (char)));
  158. }
  159. #endif
  160.  
  161. qksort (array, num_elements, elt_size, qkcmp)
  162. BYTE array[];    /* the array to sort */
  163. unsigned int num_elements;    /* the number of elements in the array */
  164. int elt_size;        /* size of an element in bytes */
  165. int (*qkcmp)();    /* routine called to compare two elements
  166.          * called with: "cmp_rtn(a, b)" which are pointers
  167.          * to two elements of the array  (or pointer to pivot)
  168.          * returns -1, 0, +1 ; if a<b, a==b, a>b*/
  169. {
  170.    register BYTE *i, *j;
  171.    BYTE *i1, *lp, *rp;
  172.    BYTE *p;    /* pointer to middle elt of a segment */
  173.    BYTE *lv[18], *uv[18];    /* stack for non-recurs */
  174.    int sp;            /* stack pointer */
  175.    BYTE **lvsp, **lvsp1;    /* pointers for lv[sp] & lv[sp+1] */
  176.    BYTE **uvsp, **uvsp1;    /* pointers for uv[sp] & uv[sp+1] */
  177.    unsigned int ptr_diff;    /* the difference of 2 pointers */
  178.    unsigned int ptr_limit;    /* difference limit for seqment size */
  179.    register BYTE *jx;    /* inner index during insertionsort */
  180.    BYTE *pivot;    /*addr of a scratch area */
  181.    int loc_pivot[LOC_SIZ];    /* local pivot area for small elements */
  182.  
  183.    if (num_elements < 2) return;  /* The array is already sorted! */
  184.    move_size = elt_size;
  185.    /* see if we can move int's */
  186.    if ((((int)array & INT_MSK) == 0) && (elt_size % (sizeof(int)) == 0)) {
  187.       typ_swap = 1; /* yes, we can */
  188.       move_size = elt_size/(sizeof (int));
  189.    }
  190.    pivot = &loc_pivot;
  191.    if (elt_size > sizeof(loc_pivot))
  192.       pivot = alloc(elt_size);
  193.    sp=0;
  194.    lvsp = &lv[0]; lvsp1 = lvsp + 1;
  195.    uvsp = &uv[0]; uvsp1 = uvsp + 1;
  196.    *lvsp = array;
  197.    *uvsp = array + elt_size * (num_elements - 1);
  198.    ptr_limit = LOW_BOUND * elt_size;
  199.    while (sp >= 0) {
  200.       lp = i = *lvsp;    rp =    j = *uvsp;
  201.       ptr_diff = j-i;
  202.       if (ptr_diff < ptr_limit) { /*small segment will be handled later */
  203.      sp--; lvsp--; lvsp1--; uvsp--; uvsp1--; /* pop it off */
  204.       }
  205.       else {
  206.      /* select a pivot element & move it around. */
  207.      p = ((ptr_diff/elt_size) / 2) * elt_size + i; /* middle element */
  208.      /* mung 1st, last, middle elements around */
  209.      qswap(p, i);
  210.      i1 = i+elt_size;
  211.      if ((*qkcmp)(i1, j) > 0) qswap(i1, j);
  212.      if ((*qkcmp)(i, j) > 0) qswap(i, j);
  213.      if ((*qkcmp)(i1, i) > 0) qswap(i1, i);
  214.      i = i1;
  215. /* Get things on the proper side of the pivot.
  216.  * The above munging around has cleverly set up the boundary conditions
  217.  * so that we don't need to check the pointers against the partition
  218.  * limits. So the inner loop is very fast.
  219. */
  220.      for (;;) {
  221.         do (i += elt_size);  while ((*qkcmp)(i, lp) < 0);
  222.         do (j -= elt_size);  while ((*qkcmp)(lp, j) < 0);
  223.         if (j < i) break;
  224.         qswap(i, j);
  225.      }
  226.      qswap(lp, j);
  227. /* done with this partition */
  228.      if ( (j-lp) < (rp-j)) { /* stack so shorter is done first */
  229.         *lvsp1 = *lvsp;
  230.         *uvsp1 = j-elt_size;
  231.         *lvsp = j+elt_size;
  232.         sp++;  lvsp++;  lvsp1++;   uvsp++;   uvsp1++; /* push stack */
  233.      }
  234.      else {
  235.         *lvsp1 = j+elt_size;
  236.         *uvsp1 = *uvsp;
  237.         *uvsp = j-elt_size;
  238.         sp++;  lvsp++;  lvsp1++;   uvsp++;   uvsp1++; /* push stack */
  239.  
  240.      }
  241.       }
  242.    }
  243. /* Now do an insertionsort to get the small segments (which were
  244.  * bypassed earlier) sorted.
  245. */
  246.    p = array + elt_size * (num_elements - 1);    /* last element of array */
  247.    for (i=array, j=i+elt_size; i<p; i=j, j+=elt_size) {
  248.       if ((*qkcmp)(i,j) > 0) { /*we have hit an out-of-sort area */
  249.      memcopy(pivot, j, elt_size);
  250.      for (jx=j; (i >= array) && ((*qkcmp)(i,pivot) > 0)
  251.         ; jx=i, i-=elt_size) {
  252.         memcopy(jx, i, elt_size);
  253.      }
  254.      memcopy(jx, pivot, elt_size);
  255.       }
  256.    }
  257.    if (elt_size > sizeof(loc_pivot))
  258.       free(pivot);
  259. }
  260.  
  261. /************************/
  262. /** swap routine ****/
  263. static qswap(a, b)
  264. register int *a, *b;
  265. {
  266.    register int i;
  267. #ifdef AMIGA
  268.    register char *ac, *bc;
  269. #endif
  270.    register int t;
  271.    register char tc;
  272.  
  273.    if (typ_swap != 0) {    /* move an int at a time */
  274.       for (i = move_size; i--; ) {
  275.      t = *a; *a++ = *b;    *b++ = t;
  276.       }
  277.    }
  278.    else {        /* move a byte at a time */
  279. #ifdef AMIGA        /* compiler braindamage */
  280.       ac = a;  bc = b;
  281.       for (i = move_size; i--; ) {
  282.      tc = *ac;
  283.      *ac++ = *bc;
  284.      *bc++ = tc;
  285.       }
  286. #else
  287.       for (i = move_size; i--; ) {
  288.      tc = *(char *)a;
  289.      *((char *)a)++ = *(char *)b;
  290.      *((char *)b)++ = tc;
  291.       }
  292. #endif
  293.    }
  294. }
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306. #ifdef TRYMAIN
  307. #define LOOPCNT 5    /* number of times to go around */
  308.  
  309. #ifdef wsm
  310. #include <std.h>
  311. #else
  312. #include <stdio.h>
  313. #endif
  314.  
  315. #define SSIZE 5000
  316. extern long int systime();    /* msec since midnight */
  317. extern long int random();
  318. extern int compare();
  319. long int s_time = 0;        /* start time */
  320.  
  321. int array[SSIZE] = 0;        /* the array to sort */
  322. int stmp = 0;
  323. int lcnt = LOOPCNT;        /* # of times to go around */
  324.  
  325. long int cswap = 0;        /* swap count */
  326. long int ccomp = 0;        /* compare count */
  327. long int ccopy = 0;        /* copy count */
  328.  
  329. main()
  330. {
  331.    register int i;
  332.  
  333.    randinit(0);
  334.    while (lcnt--) {
  335.       for (i=0; i<SSIZE; i++)
  336.      array[i] = random() & 077777;
  337.       i = isort();
  338.       printf("Sort rand elapsed: %d.%0.1d sec\n", i/10, i%10);
  339.       printf ("swap:%ld   comp:%ld   copy:%ld\n", cswap, ccomp, ccopy);
  340.       cswap = ccomp = ccopy =0;
  341.    }
  342.    lcnt = LOOPCNT;
  343.  
  344.    randinit(0);
  345.    while (lcnt--) {
  346.       for (i=0; i<SSIZE; i++)
  347.      array[i] = random() % (SSIZE/100);
  348.       i = isort();
  349.       printf("Sort many eq elapsed: %d.%0.1d sec\n", i/10, i%10);
  350.       printf ("swap:%ld   comp:%ld   copy:%ld\n", cswap, ccomp, ccopy);
  351.       cswap = ccomp = ccopy =0;
  352.    }
  353.    lcnt = LOOPCNT;
  354.  
  355.    randinit(0);
  356.    while (lcnt--) {
  357.       for (i=0; i<SSIZE; i++)
  358.      array[i] = random() & 077777;
  359.       isort();
  360.       i = isort();
  361.       printf("Sort sorted elapsed: %d.%0.1d sec\n", i/10, i%10);
  362.       printf ("swap:%ld   comp:%ld   copy:%ld\n", cswap, ccomp, ccopy);
  363.       cswap = ccomp = ccopy =0;
  364.    }
  365.    lcnt = LOOPCNT;
  366. }
  367.  
  368. isort()
  369. {
  370.    int j;
  371.    register int i;
  372.  
  373.    s_time = systime();
  374.    qksort(array, SSIZE, sizeof(array[0]), &compare);
  375.    j = (systime() - s_time) / 100;
  376.    for (i=0; i<SSIZE-1; i++) {
  377.       if (array[i] > array[i+1]) {
  378.      printf("Not in sort.\n");
  379.      break;
  380.       }
  381.    }
  382.    return (j);
  383. }
  384.  
  385. /* compare routine  */
  386. compare(a,b)
  387. int *a, *b;
  388. {
  389.    ccomp++;
  390.    return (*a - *b);
  391. }
  392. #endif
  393.  
  394.